import java.util.Scanner;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-10-19
 * Time:11:37
 */
//Stack栈练习题

//最小栈
//设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
//实现 MinStack 类:
//MinStack() 初始化堆栈对象。
//void push(int val) 将元素val推入堆栈。
//void pop() 删除堆栈顶部的元素。
//int top() 获取堆栈顶部的元素。
//int getMin() 获取堆栈中的最小元素。
class MinStack {
    public Stack<Integer> stack;
    public Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    //入栈
    public void push(int val) {
        stack.push(val);
        if (minStack.empty()) {
            minStack.push(val);
        }else {
            int peekVal = minStack.peek();
            if (val <= peekVal) {
                minStack.push(val);
            }
        }
    }
    //出栈
    public void pop() {
        if (stack.empty()) {
            return;
        }
        int popVal = stack.pop();
        if (popVal == minStack.peek()) {
            minStack.pop();
        }
    }
    //获取栈顶元素-获取的是普通栈stack栈顶的元素
    public int top() {
        if (stack.empty()) {
            return -1;
        }
        return stack.peek();
    }
    //获取栈中的最小元素-获取的是最小栈minSTack栈顶的元素
    public int getMin() {
        if (minStack.empty()) {
            return -1;
        }
        return minStack.peek();
    }

    @Override
    public String toString() {
        return "MinStack{" +
                "stack=" + stack +
                ", minStack=" + minStack +
                '}';
    }
}

public class Test {
    public static void main(String[] args) {
        //最小栈
        MinStack minStack = new MinStack();
        minStack.push(-1);
        minStack.push(0);
        minStack.push(-2);
        minStack.push(1);
        minStack.push(-2);

        System.out.println(minStack);//stack=[-1, 0, -2, 1, -2], minStack=[-1, -2, -2]

        minStack.pop();           //stack=[-1, 0, -2, 1], minStack=[-1, -2]
        //minStack.pop();           //stack=[-1, 0, -2], minStack=[-1, -2]
        System.out.println(minStack);

        System.out.println(minStack.top());

        System.out.println(minStack.getMin());
    }

    //栈的压入、弹出序列/出栈入栈次序匹配
    //输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
    //例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
    public static boolean isPopOrder(int[] pushV,int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            while (!stack.isEmpty() && j < popV.length && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }

    public static void main3(String[] args) {
        int[] pushV = {1,2,3,4,5};
        int[] popV = {4,5,3,2,1};
        System.out.println(isPopOrder(pushV, popV));
    }
    //逆波兰表达式求值（后缀表达式）
    //给你一个字符串数组 tokens ，表示一个根据逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
    //有效的算符为 '+'、'-'、'*' 和 '/'
    /*
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (!isOperator(tokens[i])) {
                int val = Integer.parseInt(tokens[i]);
                stack.push(val);
            }else {
                int val2 = stack.pop();
                int val1 = stack.pop();
                switch (tokens[i]) {
                    case "+":
                        stack.push(val1+val2);
                        break;
                    case "-":
                        stack.push(val1-val2);
                        break;
                    case "*":
                        stack.push(val1*val2);
                        break;
                    case "/":
                        stack.push(val1/val2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    */
    public static int evalRPN(String[] tokens) {
       Stack<Integer> stack = new Stack<>();
       for (String s : tokens) {
           if (!isOperator(s)) {
               int x = Integer.parseInt(s);////如果s不是操作符，就将数字字符串先转化为整数类型
               stack.push(x);//然后再保存到栈中
           }else {
               //如果s是操作符，将栈中的2个元素出栈，选择正确的操作符计算结果
               int val2 = stack.pop();
               int val1 = stack.pop();
               switch (s) {
                   case "+":
                       stack.push(val1+val2);
                       break;
                   case "-":
                       stack.push(val1-val2);
                       break;
                   case "*":
                       stack.push(val1*val2);
                       break;
                   case "/":
                       stack.push(val1/val2);
                       break;
               }
           }
       }
       return stack.pop();//最终栈中的元素是整个表达式的最终结果，将其出栈
    }
    //检查是否是有效的运算符
    private static boolean isOperator(String str) {
        if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
            return true;
        }
        return false;
    }

    public static void main2(String[] args) {
        String[] tokens = {"2","1","+","3","*"};
        int ret = evalRPN(tokens);
        System.out.println(ret);//9

        String[] array = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
        System.out.println(evalRPN(array));//22
    }
    //有效括号/括号匹配
    //给定一个只包括 '(' , ')' , '{' , '}' , '[' , ']' 的字符串 s ，判断字符串是否有效。
    //有效字符串需满足：
    //1.左括号必须用相同类型的右括号闭合。2.左括号必须以正确的顺序闭合。3.每个右括号都有一个对应的相同类型的左括号。
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);//栈中放左括号 （ { [
            }else {
                //栈空，但是字符串没有遍历完成的情况，说明右括号多了/或者此时根本就还没有往栈中放入元素，说明第一个字符是右边的括号
                if (stack.isEmpty()) {
                    System.out.println("括号不匹配！");
                    return false;
                }
                //此时开始判断是否匹配
                char ch1 = stack.peek();
                if (ch == ')' && ch1 == '(' || ch == '}' && ch1 == '{' || ch == ']' && ch1 == '[') {
                    stack.pop();
                }else {
                    System.out.println("括号不匹配！");
                    return false;
                }
            }
        }
        //走到这里，栈没有空，但是字符串已经遍历完了，说明左括号多了
        if (!stack.isEmpty()) {
            System.out.println("括号不匹配！");
            return false;
        }

        System.out.println("括号匹配!");
        return true;//走到这里，说明正确匹配了（栈空&&字符串遍历完成 ）
    }

    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入字符串内容：");
        String s = scanner.nextLine();//1.s = "()[]{}" 2.s = "(]" 3.s = "()" 4.s = "([])" 5.s = "([)]"

        System.out.println(isValid(s));
    }
}
